package linkedList;

import java.util.Stack;

public class SingLinkedList {
    public static void main(String[] args) {
        //测试
        HeroNode heroNode1 = new HeroNode(1, "宋江", "及时雨");
        HeroNode heroNode2 = new HeroNode(2, "卢俊义", "玉麒麟");
        HeroNode heroNode3 = new HeroNode(3, "吴用", "智多星");

        SingLinkedListDemo singLinkedList = new SingLinkedListDemo();

        singLinkedList.addByOrder(heroNode3);
        singLinkedList.addByOrder(heroNode2);
        singLinkedList.addByOrder(heroNode1);
        singLinkedList.addByOrder(heroNode3);
        //获取节点数量
        int length = singLinkedList.getLength(singLinkedList.getHead());
        System.out.printf("节点个数为%d。" + '\n', length);
        //测试修改
        HeroNode heroNode = new HeroNode(1, "晁盖", "天王");
        //测试查找倒数第n个节点
        singLinkedList.showLinkedList();
        HeroNode lastNode = singLinkedList.findLastNode(singLinkedList.head, 1);
        System.out.println("倒数第1个节点为" + lastNode);
        singLinkedList.undate(heroNode);
        System.out.println("测试删除");
        singLinkedList.remove(5);
        singLinkedList.remove(2);
        singLinkedList.remove(1);
        singLinkedList.remove(3);
        singLinkedList.showLinkedList();

        System.out.println("测试反转");
        singLinkedList.add(new HeroNode(1, "宋江", "及时雨"));
        singLinkedList.add(new HeroNode(2, "卢俊义", "玉麒麟"));
        singLinkedList.add(new HeroNode(3, "吴用", "智多星"));
        singLinkedList.reverse(singLinkedList.head);
        singLinkedList.showLinkedList();

        System.out.println("测试反转打印");
        singLinkedList.reversePrint(singLinkedList.head);

        System.out.println("测试合并");
        SingLinkedListDemo singLinkedList1 = new SingLinkedListDemo();
        singLinkedList.add(new HeroNode(1, "宋江", "及时雨"));
        singLinkedList.add(new HeroNode(2, "卢俊义", "玉麒麟"));
        SingLinkedListDemo singLinkedList2 = new SingLinkedListDemo();
    }

    //定义链表
    static class SingLinkedListDemo {
        //建立头节点
        private HeroNode head = new HeroNode(0, "", "");

        //返回头节点
        public HeroNode getHead() {
            return head;
        }

        //添加节点
        public void add(HeroNode node) {
            //头节点不能动
            HeroNode temp = head;
            //遍历找到最后一个节点
            while (true) {
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            //指向新的节点
            temp.next = node;
        }


        //按照no排序添加节点
        public void addByOrder(HeroNode node) {
            //头节点不能动
            HeroNode temp = head;
            boolean flag = false;
            //遍历
            while (true) {
                if (temp.no == node.no) {
                    flag = true;
                    break;
                }
                if (temp.next == null || temp.next.no > node.no) {
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                System.out.printf("已有排名为%d的好汉，无法添加。" + '\n', node.no);
            } else {
                //指向新的节点
                node.next = temp.next;
                temp.next = node;
            }

        }

        //修改节点
        public void undate(HeroNode node) {
            //头节点不能动
            HeroNode temp = head;
            if (temp == null) {
                System.out.println("链表为空");
            }
            boolean flag = false;
            //遍历
            while (true) {
                if (temp.no == node.no) {
                    flag = true;
                    break;
                }
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                temp.name = node.name;
                temp.nickname = node.nickname;
            } else {
                System.out.printf("没有找到排名为%d的好汉，无法修改。" + '\n', node.no);
            }

        }

        //删除节点
        public void remove(int no) {
            //头节点不能动
            HeroNode temp = head;
            if (temp == null) {
                System.out.println("链表为空");
            }
            boolean flag = false;
            //遍历
            while (true) {
                if (temp.next == null) {
                    break;
                }
                if (temp.next.no == no) {
                    flag = true;
                    break;
                }
                temp = temp.next;
            }
            if (flag) {
                temp.next = temp.next.next;//被删除的节点，没有引用后会被gc清理。
            } else {
                System.out.printf("没有找到排名为%d的好汉,无法删除。" + '\n', no);
            }

        }

        //显示链表
        public void showLinkedList() {
            if (head.next == null) {
                System.out.println("链表为空");
                return;
            }
            //头节点不能动
            HeroNode temp = head.next;
            //遍历找到最后一个节点
            while (true) {
                System.out.println(temp);
                if (temp.next == null) {
                    break;
                }
                temp = temp.next;
            }
        }

        //获取节点数量
        public int getLength(HeroNode node) {
            if (node.next == null) {
                return 0;
            }
            int length = 0;
            //不统计头节点
            HeroNode cur = node.next;
            while (cur != null) {
                length++;
                cur = cur.next;
            }
            return length;
        }

        //查找链表中倒数第k个节点
        public HeroNode findLastNode(HeroNode head, int k) {
            if (head.next == null || k <= 0) {
                return null;
            }
            int length = getLength(getHead());
            if (length < k) {
                return null;
            }
            HeroNode cur = head.next;
            int count = 0;
            while (cur != null) {
                if (count == (length - k)) {
                    break;
                }
                count++;
                cur = cur.next;
            }
            return cur;
        }

        //单链表反转
        public void reverse(HeroNode head) {
            if (head.next == null || head.next.next == null) {
                return;
            }
            HeroNode cur = head.next;
            HeroNode node = null;
            HeroNode reverseNode = null;
            while (cur != null) {
                node = new HeroNode(cur.no, cur.name, cur.nickname);
                node.next = reverseNode;
                reverseNode = node;
                cur = cur.next;
            }
            head.next = reverseNode;
        }

        //单链表反向打印
        public void reversePrint(HeroNode head) {
            if (head.next == null || head.next.next == null) {
                return;
            }
            Stack<HeroNode> nodes = new Stack<>();
            HeroNode cur = head.next;
            while (cur != null) {
                nodes.push(cur);
                cur = cur.next;
            }
            int size = nodes.size();
            for (int i = 0; i < size; i++) {
                HeroNode pop = nodes.pop();
                System.out.println(pop);
            }
        }

        //单链表合并
        public void merge(SingLinkedListDemo demo) {
            if (demo == null) {
                return;
            }
            HeroNode cur = demo.getHead().next;
            while (cur != null) {
                addByOrder(cur);
                cur = cur.next;
            }
        }
    }


    //定义节点
    static class HeroNode {
        private int no;//排名
        private String name;//名字
        private String nickname;//名号
        private HeroNode next;//指向下一个节点


        public HeroNode(int hno, String hname, String hnickname) {
            this.no = hno;
            this.name = hname;
            this.nickname = hnickname;
        }

        @Override
        public String toString() {
            return "HeroNode{" +
                    "no=" + no +
                    ", name='" + name + '\'' +
                    ", nickname='" + nickname + '\'' +
                    '}';
        }
    }
}
